// 《围棋》作者版权所有。保留所有权利。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

package flate

// dictDecoder实现了用于解压的LZ77滑动字典。
// LZ77通过两种形式的命令序列来解压数据：
// 
// *文字插入：一个或多个符号的运行按原样插入到数据
// 流中。这是通过
// 单个符号的writeByte方法实现的，或通过多个符号的writeSlice/writeMark组合实现的。
// 如果未使用预设字典
// 任何有效流都必须以文字插入开头。
// 
// *反向复制：一个或多个符号的运行是从之前的
// 发射的数据中复制的。反向拷贝以元组（dist，length）的形式出现，其中dist 
// 决定从流中向后拷贝多远，length决定
// 要拷贝多少字节。请注意，长度大于
// 距离是有效的。由于LZ77使用前向拷贝，这种情况被用于
// 对符号的重复运行执行一种形式的游程编码。
// writeCopy和tryWriteCopy用于实现该命令。
// 
// 出于性能原因，此实现几乎不执行健全的
// 检查参数。因此，必须遵守为每个
// 方法调用记录的不变量。
type dictDecoder struct {
	hist []byte // 滑动窗口历史

	// 不变量：0<=rdPos<=wrPos<=len（hist）
	wrPos int  // 缓冲区中的当前输出位置
	rdPos int  // 已发出hist[：rdPos]
	full  bool // 是否已写入完整的窗口长度？
}

// init初始化dictDecoder，使其具有给定
// 大小的滑动窗口字典。如果提供了预设的dict，它将用
// 初始化字典。
func (dd *dictDecoder) init(size int, dict []byte) {
	*dd = dictDecoder{hist: dd.hist}

	if cap(dd.hist) < size {
		dd.hist = make([]byte, size)
	}
	dd.hist = dd.hist[:size]

	if len(dict) > len(dd.hist) {
		dict = dict[len(dict)-len(dd.hist):]
	}
	dd.wrPos = copy(dd.hist, dict)
	if dd.wrPos == len(dd.hist) {
		dd.wrPos = 0
		dd.full = true
	}
	dd.rdPos = dd.wrPos
}

// histSize报告字典中的历史数据总量。
func (dd *dictDecoder) histSize() int {
	if dd.full {
		return len(dd.hist)
	}
	return dd.wrPos
}

// availRead报告readFlush可以刷新的字节数。
func (dd *dictDecoder) availRead() int {
	return dd.wrPos - dd.rdPos
}

// availWrite报告输出缓冲区空间的可用量。
func (dd *dictDecoder) availWrite() int {
	return len(dd.hist) - dd.wrPos
}

// writeSlice返回可用缓冲区的一个片段以写入数据。
// 
// 此不变量将被保留：len（s）<=availWrite（）
func (dd *dictDecoder) writeSlice() []byte {
	return dd.hist[dd.wrPos:]
}

// writeMark按cnt前进写入器指针。
// 
// 必须保持此不变量：0<=cnt<=availWrite（）
func (dd *dictDecoder) writeMark(cnt int) {
	dd.wrPos += cnt
}

// writeByte将单个字节写入字典。
// 
// 必须保持此不变量：0<availWrite（）
func (dd *dictDecoder) writeByte(c byte) {
	dd.hist[dd.wrPos] = c
	dd.wrPos++
}

// writeCopy将给定（距离、长度）的字符串复制到输出。
// 返回复制的字节数，如果输出缓冲区中的可用空间太小，则可能小于请求的
// 长度。
// 
// 必须保留此不变量：0<dist<=histSize（）
func (dd *dictDecoder) writeCopy(dist, length int) int {
	dstBase := dd.wrPos
	dstPos := dstBase
	srcPos := dstPos - dist
	endPos := dstPos + length
	if endPos > len(dd.hist) {
		endPos = len(dd.hist)
	}

	// 在目标位置后复制非重叠部分。
	// 
	// 本节不重叠，因为本节的复制长度
	// 始终小于或等于向后距离。如果距离指的是环绕在缓冲区中的数据，则可能会发生这种情况。
	// 因此，此处执行反向复制；也就是说，在
	// 中，拷贝之前的源被放置在目标中。
	if srcPos < 0 {
		srcPos += len(dd.hist)
		dstPos += copy(dd.hist[dstPos:endPos], dd.hist[srcPos:])
		srcPos = 0
	}

	// 在目标位置之前复制可能重叠的部分。
	// 
	// 如果此段的复制长度大于向后距离，则此段可能重叠。LZ77允许这样做，因此重复的
	// 字符串可以使用（dist，length）对简洁地表示。
	// 因此，此处执行转发复制；也就是说，复制的字节是
	// 可能取决于复制
	// 过程中目标中产生的字节。这在功能上等同于：对于i:=0，
	// 
	// ；i<endPos-dstPos；i++{
	// dd.hist[dstPos+i]=dd.hist[srcPos+i]
	// }
	// /dstPos=endPos 
	// 
	for dstPos < endPos {
		dstPos += copy(dd.hist[dstPos:endPos], dd.hist[srcPos:dstPos])
	}

	dd.wrPos = dstPos
	return dstPos - dstBase
}

// tryWriteCopy尝试将给定（距离、长度）的字符串复制到
// 输出。这个专门的版本针对短距离进行了优化。
// 
// 出于性能原因，此方法设计为内联。
// 
// 必须保留此不变量：0<dist<=histSize（）
func (dd *dictDecoder) tryWriteCopy(dist, length int) int {
	dstPos := dd.wrPos
	endPos := dstPos + length
	if dstPos < dist || endPos > len(dd.hist) {
		return 0
	}
	dstBase := dstPos
	srcPos := dstPos - dist

	// 在目标位置之前复制可能重叠的部分。
	for dstPos < endPos {
		dstPos += copy(dd.hist[dstPos:endPos], dd.hist[srcPos:dstPos])
	}

	dd.wrPos = dstPos
	return dstPos - dstBase
}

// readFlush返回准备发送给用户的历史缓冲区的一部分。在调用任何其他dictDecoder方法之前，必须完全使用readFlush返回的数据
// 。
func (dd *dictDecoder) readFlush() []byte {
	toRead := dd.hist[dd.rdPos:dd.wrPos]
	dd.rdPos = dd.wrPos
	if dd.wrPos == len(dd.hist) {
		dd.wrPos, dd.rdPos = 0, 0
		dd.full = true
	}
	return toRead
}
